//Given an m x n integers matrix, return the length of the longest increasing pa
//th in matrix. 
//
// From each cell, you can either move in four directions: left, right, up, or d
//own. You may not move diagonally or move outside the boundary (i.e., wrap-around
// is not allowed). 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[9,9,4],
//                 [6,6,8],
//                 [2,1,1]]
//Output: 4
//Explanation: The longest increasing path is [1, 2, 6, 9].
// 
//
// Example 2: 
//
// 
//Input: matrix = [[3,4,5],
//                 [3,2,6],
//                 [2,2,1]]
//Output: 4
//Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is
// not allowed.
// 
//
// Example 3: 
//
// 
//Input: matrix = [[1]]
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 200 
// 0 <= matrix[i][j] <= 231 - 1 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 动态规划 
// 👍 579 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Longest Increasing Path in a Matrix
public class P329LongestIncreasingPathInAMatrix {
    public static void main(String[] args) {
        Solution solution = new P329LongestIncreasingPathInAMatrix().new Solution();
        System.out.println(solution.longestIncreasingPath(new int[][]{{3, 4, 5},
                {3, 2, 6},
                {2, 2, 1}}));
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int rowLen = 0;
        int colLen = 0;
        int[][] graph;
        boolean[][] visted;
        int max = 1;

        public int longestIncreasingPath(int[][] matrix) {
            graph = matrix;
            rowLen = matrix.length;
            colLen = matrix[0].length;
            visted = new boolean[rowLen][colLen];
            for (int i = 0; i < rowLen; i++) {
                for (int j = 0; j < colLen; j++) {
                    max = Math.max(max, search(i, j, new ArrayList<>()));
                }
            }
            return max;
        }

        private int search(int col, int row, List<Integer> path) {
            if (path.size() > 1) {
                if (path.get(path.size() - 2) >= path.get(path.size() - 1)) {
                    return path.size() - 1;
                }
            }
            int[] index = {0, -1, 1};
            for (int i = 0; i < index.length; i++) {
                for (int j = 0; j < index.length; j++) {
                    if (i != j || (i == j && i == 0)) {
                        int i1 = row + index[i];
                        int j1 = col + index[j];
                        if (0 <= i1 && i1 < rowLen) {
                            if (0 <= j1 && j1 < colLen) {
                                if (!visted[i1][j1]) {
                                    path.add(graph[i1][j1]);
                                    visted[i1][j1] = true;
                                    max = Math.max(max, search(i1, j1, path));
                                    visted[i1][j1] = false;
                                    path.remove(path.size() - 1);
                                }
                            }
                        }
                    }
                }
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}